#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
class Solution {
public:
    string reverseWords(string s) {
        // ① 翻转所有单词
        reverse(s.begin(),s.end());

        // ② 翻转每一个单词
        int start = 0;
        int end = 0;
        for(int i = 0;i < s.size();++ i)
        {
            if(s[i] != ' ')
            {
                start = i;
                int j;
                int alphaNum = 0;
                for(j = i;j < s.size();++ j)
                {
                    if(s[j] == ' ') break;
                    ++ alphaNum;
                }
                end = start + alphaNum;

                reverse(s.begin() + start,s.begin() + end);
                i = j;
            }
        }

        // ③ 去除空格

        int slow = 0;
        int fast = 0;
        for(int i = 0;i < s.size(); ++ i)
        {
            if(s[i] != ' ') 
            {
                if(slow != 0) s[slow ++] = ' ';
                while (s[fast] != ' ')
                {
                    s[slow ++] = s[fast ++];
                    i ++;
                    if(fast == s.size()) break;
                }
                i --;
            }
            else
            {
                ++ fast;
            }
        }
        s.resize(slow);
        return s;
    }   
};

int main(int argc, char const *argv[])
{
    Solution s;
    string str = s.reverseWords("  hello world  ");
    cout << str << "\n";
    return 0;
}
